package com.example.demo.leetcode.zuocheng.btree;

import com.example.demo.leetcode.zuocheng.graph.Node;

/**
 *
 * 思路:
 *      将二叉树每个节点值 和 父节点的值 存入Map
 *      取其中一个节点，遍历Map将所有的值存入Set，
 *      遍历另一个节点，遍历Map与Set比较，第一个出现在Set中的值则是公共祖先
 *      O(n) 效率一般
 *
 *      方法二:
 *      找 o1 o2 两个的公共祖先， 在X树中
 *      定义类 Info:
 *             Node x  找到的公共祖先
 *             boolean findO1 左树上发现了o1
 *             boolean findO2 右树上发现了o2
 *      遍历整颗树:
 *      统计每个节点的Info信息
 *      (1) root == null 返回 Info(null,false,false)
 *      (2) findO1 = x==o1 || 做子树找到O1 || 右子树找到O1
 *          findO2 = x==o2 || 左子树找到O2 || 由子树找到O2
 *      (3)判断结果
 *         (1)先判断子树是否找到公共祖先
 *         (2)子树没有找到公共祖先，判断当前节点是否是公共祖先
 *
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/9/12 10:55
 */
public class Btree_二叉树的最近公共祖先 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


    public static class Info{
        TreeNode x;
        boolean findO1;
        boolean findO2;

        public Info(TreeNode x, boolean findO1, boolean findO2) {
            this.x = x;
            this.findO1 = findO1;
            this.findO2 = findO2;
        }
    }


    public static TreeNode findParentNode(TreeNode x,int o1 ,int o2){
        Info process = process(x, o1, o2);
        return process.x;
    }

    public static Info process(TreeNode x,int o1 ,int o2){

        if(x == null){
            return new Info(null,false,false);
        }

        Info leftInfo = process(x.left,o1,o2);
        Info rightInfo = process(x.right,o1,o2);
        boolean findO1 = x.val == o1 || leftInfo.findO1 || rightInfo.findO1;
        boolean findO2 = x.val == o2 || leftInfo.findO2 || rightInfo.findO2;

        TreeNode res = null;
        if(leftInfo.x != null){
            res = leftInfo.x;
        }
        if(rightInfo.x != null){
            res = rightInfo.x;
        }
        if(res == null){
            if(findO1 && findO2){
                res = x;
            }
        }
        return new Info(res,findO1,findO2);

    }




}
